1. Field of the Invention
The present invention relates to a turbo decoder, a turbo decoding method, and an operating program of the same and more particularly to improvements in a high-performance and high-reliability turbo decoding method to decode a turbo code to be used in fields of communication systems and information processing systems.
The present application claims priority of Japanese Patent Application No. 2004-012540 filed on Jan. 21, 2004, which is hereby incorporated by reference.
2. Description of the Related Art
In recent years, a turbo code method which uses a so-called turbo code as an error-correcting code enabling a characteristic being near to the Shannon limit to be obtained is being studied and developed by C. Berrou et. al., as a high-performance and high-reliability coding method to be used in a wide range of communications and information processing including a mobile telecommunication system, information storage system, digital broadcasting system, and a like.
First, a general turbo encoder and a general turbo decoder are described. FIGS. 6 and 7 are schematic diagrams showing configurations of a publicly known conventional turbo encoder and a publicly known conventional turbo decoder. FIG. 6 shows the schematic block diagram showing the turbo encoder having a coding rate of ⅓, which includes Recursive Systematic Convolutional Encoders (may be simply referred to as element encoders) E11 and E22, and an interleaver E21. A “sequence of information bits to be encoded” (hereinafter, may be referred to as “information bit to be encoded”) E01 is branched to be output as a sequence of systematic bits (hereinafter, may be simply referred to as systematic bit) E02 and to be input to the element encoder E11 and the interleaver E21.
The element encoder E11 encodes the “information bit to be encoded” E01 by using an error-correcting code, to output a sequence of redundancy bits (hereinafter, may be simply referred to as parity bit) E12. The interleaver E21 generally writes once the “information bit to be encoded” E01, reads out the “information bit to be encoded” E01 in a different order, and then transfers to the element encoder E22 with data being arranged in a mixed order. The element encoder E22 encodes the interleaved sequence of an information bit to be encoded by using element data and outputs a sequence of redundancy bits (hereinafter, may be simply referred to as parity bit) E23. In ordinary cases, as the element encoders E11 and E22, a recursive systematic convolutional encoder (RSC) is employed.
The turbo decoder shown in FIG. 7 includes element decoders D04 and D16, an interleaver D12, a de-interleaver D23, and a hard decision and decoder output block D25. To the element decoder D04 are input a systematic information sequence (hereinafter, may be simply referred to as systematic information) D01 corresponding to the systematic bit E02 and a parity information sequence (may simply referred to as parity information) D02 corresponding to the parity bit E12, and extrinsic information D03. Then, output extrinsic information D11 is used by the subsequent element decoder D16.
Moreover, the obtained extrinsic information D11 and the systematic information D01 are input to the element decoder D16, as extrinsic information D15 and the systematic information D13 through the interleaver D12, together with a parity information sequence (may be simply referred to as parity information) D14 corresponding to the parity bit E23. Then, soft output information D21 and extrinsic information D22 obtained by the element decoder D16 are transferred to the de-interleaver D23.
The de-interleaver D23 outputs information in order being reverse to order of interchanging of data made by the interleaver D12. That is, the order of each of the interleaved soft output information D21 and the extrinsic information D22 is made to get into its original order arranged before having been interleaved and the information is output as soft decision output information D24 and extrinsic information D03. Moreover, the hard decision and decoder output block D25 makes a hard decision on the soft decision output information D24 to output a final decoded result. The extrinsic information D03 is fed back to the element decoder D04 for subsequent decoding processing.
As described above, in the turbo decoder shown in FIG. 7, the decoding processing is repeated by renewing extrinsic information D15 from the element decoder D04 and the extrinsic information D03 from the element decoder D16 and, after a plurality of times of loop operations, a hard decision is made on the soft decision output information D24.
As a soft output decoding algorithm to be applied to the element decoder for turbo decoding, a MAP (Maximum A Posteriori Probability) decoding method is reported to be the best at present. However, this method has problems in that a device to perform this method becomes very large in size and an amount of processing is remarkably large and, therefore, in an actual installation, a Max-Log-MAP (Max Logarithmic Maximum A Posteriori) method in which the processing is simplified by judging whether transmitted data is “1” or “0” based on a maximum value of likelihood is generally and widely used.
A MAP algorithm is a maximum likelihood decoding algorithm using a trellis diagram. FIG. 8A is a diagram illustrating an example of an element encoder which shows a case in which the number of registers “D” is three. The trellis diagram, as shown in FIG. 8B, represents a relation between a value output when a value is input to the element encoder and a state of each of the registers “D”.
The MAP algorithm roughly includes following three kinds of processing:    (a) Forward processing: To calculate a probability (forward path metric value) of reaching from a head of the trellis diagram to each state at each time point.    (b) Backward processing: To calculate a probability (backward path metric value) of reaching from an end of the trellis diagram to each state at each time point.    (c) Soft output generating processing and extrinsic value calculating processing: To calculate a soft output value of a systematic bit at each time point using results from the above processing (a) and (b) and further to calculate an extrinsic value using the soft output value.
In the trellis diagram, a forward path metric value and a backward path metric value to be calculated in each of forward and backward processing operations at a time point “t” (not shown) and in a state “s” (not shown) are represented as an Alpha value (t, s) (not shown) and Beta value (t, s) (not shown), respectively. Furthermore, a probability of transition from the state “s” to a state “s′” at the time point “t” is represented as a Gamma value (t, s, s′) (here, the Gamma is called a “branch metric value”). The Gamma value (t, s, s′) (not shown) is a probability that can be obtained from received values (systematic information sequence, parity information sequence, and extrinsic information).
Each of the forward processing operation, backward processing operation, soft output generating processing operation and extrinsic value calculating processing operation described above is performed as follows:
(a) Forward Processing Operation:Alpha(t, s)=Max{Alpha(t−1, s′)+Gamma(t, s′, s)}  Equation 1
Here, in the above equation 1, the “Max” indicating the processing of obtaining a maximum value shows that the maximum value is to be calculated in all states “s′”.
As shown in FIG. 9A, the Alpha value (t, S3) corresponding to a state (S3) at a time point “t” is calculated as follows. Out of metric values obtained by adding each of the Gamma branch metric values (t, S1, S3) and (t, S2, S3) to each of the Alpha path metric values (t−1, S1) and (t−1, S2) in two previous stages, the metric value being larger is determined as an Alpha value in the state [this calculation is called “Alpha ACS (Add-Compare-Select) calculation”]. This processing is performed in all states during all time change “t” and the Alpha values in all states are held.
Moreover, in the first calculation of the Alpha value, since there exists no Alpha value in the previous stage, setting of an initial value is required. Here, since a transition always starts from the State #0 (not shown) in the trellis diagram, as an initial Alpha value, the Alpha value of the State #0 is defined as “zero (0)” and the Alpha values of other States are defined as “−MAX (Minimum value) value”.
(b) Backward Processing Operation:Beta(t, s)=Max{Beta(t+1, s′)+Gamma(t+1, s, s′)}  Equation 2
As shown in FIG. 9B, the Beta value (t, S4) corresponding to a State (S4) at a time point “t” is calculated as follows (see equation 2). Out of metric values obtained by adding each of the branch metric Gamma values (t+1, S4, S5) and (t+1, S4, and S6) to each of the Beta path metric values (t+1, S5) and (t+1, S6) in two latter stages, the metric value being larger is determined as a Beta value in the State [this calculation is called “Beta ACS (Add-Compare-Select) calculation”].
This processing is performed in all States during all time change “t” and processing of calculating a Beta value from a direction reverse to the Alpha (that is, from a trellis final State side) is performed. Moreover, in the first calculation of the Beta value, since there exists no Beta value in the latter stage, setting of an initial value is required. Here, in the final end of the trellis diagram, as an initial Beta value, the Beta value of the State #0 is defined as “zero (0)” and the Beta values of other States are defined as “−MAX (Minimum value) value”.
(c) Soft Output Generating Processing and Extrinsic Value Calculating Processing Operations:
All path metric values at the time point “t” are obtained by adding Alpha (t−1, s′), Beta (t, s), and Gamma (t, s′, s) which have been already calculated. Then, a differential between a maximum path metric value of a path having a decoded result of “0 (zero)” and a maximum path metric value of a path having a decoded result of “1” becomes a soft output value at a time point “t”
In FIG. 10, the Alpha value (4, s′), Beta value (5, s), and Gamma value (5, s′, s) are added to all combinations of (s, s′) at the time point being five. Out of the results, a maximum path metric value L0 (t) having a decoded result of “0” (zero) is obtained.
In the example, the value L0 (t=5) is expressed as follows (equation 3:
                                                                        L                ⁢                                                                  ⁢                0                ⁢                                  (                                      t                    =                    5                                    )                                            =                            ⁢                                                Alpha                  ⁢                                                                          ⁢                                      (                                                                  t                        =                        4                                            ,                                              state                        ⁢                                                                                                  ⁢                        #7                                                              )                                                  +                                                                                                      ⁢                                                Beta                  ⁢                                                                          ⁢                                      (                                                                  t                        =                        5                                            ,                                              state                        ⁢                                                                                                  ⁢                        #6                                                              )                                                  +                                                                                                      ⁢                              Gamma                ⁢                                                                  ⁢                                  (                                                            t                      =                      5                                        ,                                          state                      ⁢                                                                                          ⁢                      #7                                        ,                                          state                      ⁢                                                                                          ⁢                      #6                                                        )                                                                                        Equation        ⁢                                  ⁢        3            
On the other hand, a maximum path metric value L1 (t) having a decoded result of “1” is also obtained. In the example, the value L1 (t=5) is expressed as follows (equation 4):
                                                                        L                ⁢                                                                  ⁢                1                ⁢                                                                  ⁢                                  (                                      t                    =                    5                                    )                                            =                            ⁢                                                Alpha                  ⁢                                                                          ⁢                                      (                                                                  t                        =                        4                                            ,                                              state                        ⁢                                                                                                  ⁢                        #4                                                              )                                                  +                                                                                                      ⁢                                                Beta                  ⁢                                                                          ⁢                                      (                                                                  t                        =                        5                                            ,                                              state                        ⁢                                                                                                  ⁢                        #0                                                              )                                                  +                                                                                                      ⁢                              Gamma                ⁢                                                                  ⁢                                  (                                                            t                      =                      5                                        ,                                          state                      ⁢                                                                                          ⁢                      #4                                        ,                                          state                      ⁢                                                                                          ⁢                      #0                                                        )                                                                                        Equation        ⁢                                  ⁢        4            
A soft output value at a time point being five is calculated as follows (equation 5):L(t=5)=L0(t=5)−L1(t=5)  Equation 5
Moreover, in the Max-Log-MAP algorithm, a value obtained by deducting a channel value (value to be obtained from a received value) and an a priori value (extrinsic information to be supplied from the previous-stage decoder) from the soft output value (posteriori value) obtained as above is used as extrinsic information.
As described above, in the ideal Max-Log-MAP algorithm, operations of calculating the Alpha and Beta values are performed on all data to be decoded at the same time.
However, in the data transmission, as a data length increases, very large memory areas are required for Max-Log-MAP decoding. In particular, memory areas to store path metric information of an entire trellis are necessary. Moreover, due to an increase in a decoding length, a delay in decoding processing also increases and, therefore, it is difficult to apply the Max-Log-MAP algorithm to an actual real time system.
To solve this problem, a method called a sliding window is widely used (see A. J. Viterbi, “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes” IEEE, J. Select. Areas Commun., Vol. 16, pp. 260-264, February 1998, hereinafter called a non-patent reference 1). In this method, only likelihood information in a trellis corresponding to a window size is stored and the window position is shifted until it reaches a decoding length, which enables a great reduction of the use of memory.
Furthermore, in recent years, a method is known in which one code block (data to be decoded) is divided into a plurality of sub-code blocks and each of the sub-code blocks is decoded in parallel (see S. Yoon, Y. Bar-Ness, “A Parallel MAP Algorithm for Low Latency Turbo Decoding” IEEE Communication Letters, Vol. 6, No. 7, pp. 288-290, July 2002, hereinafter called a non-patent reference 2). In the method, since path metric values (Alpha and Beta values) at a node (between a starting point and a final point of each sub-code block) are indefinite due to simultaneous processing of each sub-decoder, an Alpha initial value of a first sub-code block (the initial value being the same as set in the ideal Max-Log-MAP algorithm) and a Beta initial value of a final sub-code block (the initial value being the same as set in the ideal Max-Log-MAP algorithm) are removed and an Alpha initial value and a Beta initial value of each sub-code block in initial decoding processing are set forcedly.
The decoder disclosed in the non-patent reference 1 has a problem in that, though enabling the great reduction of the use of memory, decoding processing is performed in order of each window and, therefore, it is impossible to reduce entire decoding processing time. The decoder disclosed in the non-patent reference 2 also has a problem in that, since all Alpha and Beta values are set as 0 (zero), decoding errors occur in a node in a concentrated manner caused by division of the sub-code blocks. Therefore, in order to realize effective and high-speed turbo decoding, improvements in initialization of parallel decoding processing are expected.